package leetcode;

import pojo.ListNode;

/**
 * 25. K 个一组翻转链表
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2022-12-23
 */
public class LeetCode25 {

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode result = getGroupEndNode(head, k);
        ListNode end = result;
        if(end == null){
            return head;
        }
        ListNode groupEndNode = groupReverse(head, end);
        ListNode kStartNode = groupEndNode.next;
        while (kStartNode != null){
            end = getGroupEndNode(kStartNode, k);
            if(end == null){
                return result;
            }
            groupEndNode.next = end;
            groupEndNode = groupReverse(kStartNode, end);
            kStartNode = groupEndNode.next;
        }
        return result;
    }

    // 得到一组中的尾节点
    public static ListNode getGroupEndNode(ListNode node, int k) {
        while (--k != 0 && node != null) {
            node = node.next;
        }
        return node;
    }

    // 组反转(返回尾节点)
    public static ListNode groupReverse(ListNode node, ListNode end) {
        ListNode head = node;
        ListNode temp = node;
        ListNode pre = end.next;
        while(head != end){
            head = node.next;
            node.next = pre;
            pre = node;
            node = head;
        }
        node.next = pre;
        return temp;
    }

    public static void main(String[] args) {
        // head = [1,2,3,4,5], k = 2
        ListNode head = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
        ListNode listNode = reverseKGroup(head, 2);
        do {
            System.out.println(listNode.val);
            listNode = listNode.next;
        } while (listNode != null);
    }

}
